The invention relates to a fast error correction circuit for binary Bose Chaudhuri Hocquenhem (BCH) codes capable of correcting up to three errors. The invention more particularly relates to a circuit that performs the second step in decoding such codes, the determination of the error-location polynomial over the Galois Field GF(2.sup.m).
It is the function of an error correcting code to repair or fix data bits that are corrupted by transmission over a communications channel without using any reference to the original transmitted data other than what is received. This is many times accomplished by breaking the data into blocks, and then inserting extra parity or check bits into each block according to a mathematical scheme; such codes are called block codes. Binary BCH codes are one type of block codes. The method of coding a BCH block or codeword consists of dividing the binary polynomial represented by the data bits in the block by a special polynomial known as the generator polynomial of the code. The method of decoding a BCH code consists of three distinct steps: 1) computing a vector known as the syndrome vector; 2) determining an error-location polynomial from the syndrome vector; 3) finding the roots of the error-location polynomial which represent the locations of the errors. The actual repair or fixing of the erroneous bits for a binary BCH code is then simply a matter of changing them to the opposite binary value i.e. one to zero, etc.
The encoding of a BCH code is strictly a binary polynomial division operation that takes place entirely in the Galois Field GF(2). Decoding on the other hand, takes place almost entirely on the extension field GF(2.sup.m), where m is a positive integer that determines the size of a codeword. Codewords are of length 2.sup.m -1. The number of data and parity bits in the codeword is determined completely by the error correcting ability of the code. The current invention is only concerned with binary BCH codes that have an error correcting ability of three errors.
The components of the syndrome vector are defined over the Galois Field GF(2.sup.m), and each can be represented in what is known as the standard representation by m binary bits. The standard representation of any Galois Field quantity uses each binary digit (bit) to indicate the presence or absence of a given power of the primitive element .alpha. over the Galois Field. The low order bit indicates the presence or absence of .alpha..sup.0 ; the next higher order bit indicates the presence or absence of .alpha..sup.1 ; the next higher order bit indicates the presence or absence of .alpha..sup.2, etc. It is well known in the theory of Galois Fields that one needs only m such bits to represent any element of the field GF(2.sup.m). For a three-error correcting BCH code, there are six components of the syndrome vector S.sub.1, S.sub.2 . . . , S.sub.6. Each of these is a Galois Field quantity. Only three of the six components are independent, as the even numbered components can always be derived from the odd numbered components by the equation S.sub.2j =S.sub.j.sup.2. Thus, the only components of the syndrome vector needed to decode any three-error correcting binary BCH code are S.sub.1, S.sub.3, and S.sub.5. These first three odd syndrome components can be computed by well known formulas from the received codeword using a straightforward process. In this invention all Galois Field quantities are represented by m+1 bits, rather than the normal m bits. The first m bits represent the quantity in the normal way in the standard representation or they represent it in a special representation more suited for field multiplication. The m plus first bit is always a zero indicator bit. It is set to one if the field quantity is zero, and it is set to zero if the field quantity is non-zero. When this bit is set, the other m bits have no meaning. In the standard representation, this bit is redundant; however, in the special representation, it is absolutely necessary, as the first m bits represent the exponent or power of the primitive field element .alpha. that yields the element. There is no power of .alpha. for the zero member of the field; hence there is no convenient way to represent zero with the first m bits (it could be represented with a unique coded pattern; however, this is not convenient). The zero indicator bit provides a very fast way to determine if the field element is zero or non-zero; it always has precedence over the other m bits. The standard representation thus represents the field element as b.sub.m-1 .alpha..sup.m-1 +b.sub.m-2 .alpha..sup.m-2 +. . . +b.sub.1 .alpha.+b.sub.0 ; the special representation represents the element with the m bit binary value equal to any positive integer between 1 and 2.sup.m -2, as the entire field consists of the elements 0,1,.alpha.,.alpha..sup.2,.alpha..sup.3, . . . ,.alpha..sup.2.spsp.m-2. Thus, for example, the field element .alpha..sup.26 is represented as the binary integer 26 in the special representation. The field element 1 is .alpha..sup.0 and is stored as 0. This obviates the need for a separate method to indicate when the desired field element is 0, as there is no power of .alpha. that equals 0. The special representation makes multiplication over the field become a modulo addition over integers, as addition of exponents is equivalent to multiplication by well-known mathematical principles. This allows very fast field multiplication.
The second decoding step, that of converting the components of the syndrome vector into the error-location polynomial, is much more difficult than the first or third steps, and is the subject of the present invention. The error-location polynomial for a three-error correcting BCH code is a third order, or lower, polynomial whose coefficients belong to the field GF(2.sup.m). This polynomial's lowest order coefficient is 1, and its roots can be directly used to find the bits that are in error in the received codeword by well known methods. Mathematically, finding this polynomial consists of solving a system of non-linear equations over the Galois field or an equivalent simplification of this process. The basic method was developed by E. Berlekamp [1] [E. R. Berlekamp, Algebraic Coding Theory, Aegean Park Press, 1984, pp. 176-184]. For the special case of binary BCH codes, an iterative algorithm exists that can find the polynomial coefficients. It was developed by Lin [2] [S. Lin, An Introduction to Error-Correcting Codes, Prentice Hall, Englewood Cliffs, N.J., 1970, pp. 122-129]. In April 1990, I published a method of converting Lin's iterative method into a descent through a binary decision tree to yield an equation for each polynomial coefficient. [3] [IEEE lnternational Conference on Communications, April 1990, C. Kraft, "Closed Solution of the Berlekamp-Massey Algorithm for Fast Decoding of BCH Codes", pp 458-462]. The invention is an embodiment of that method.
The invention can be realized as a VLSI integrated circuit or a discrete circuit that takes the first three odd components of a computed syndrome vector and produces the three non-trivial components of the error-location polynomial .sigma.(x) over GF(2.sup.m). .sigma.(x) can be written as: EQU .sigma.(x)=1+.sigma..sub.1 x+.sigma..sub.2 x.sup.2 +.sigma..sub.3 x.sup.3
The non-trivial coefficients are the coefficients of x to any positive power. The coefficient of x.sup.0 is always 1 for any error-location polynomial, and thus is considered a trivial coefficient. The circuit traverses a binary decision tree and solves formulas as I described in April 1990 [3]. The exact values of the syndrome components of any given received codeword are determined by the number of errors and are computed externally to my invention. Given the computed syndrome components, my invention makes a descent through a three-level binary tree to find the correct formulas for the polynomial coefficients. These coefficients are then computed and presented to the output port. The entire process can be performed by a combinational circuit (one having no clock) if the values of the syndrome components are held at the input port for the duration of the circuit logic delay. After this logic delay, the non-trivial coefficients of the error-location polynomial appear at the circuit's output port.
In decoding BCH codes it is very important to be able to determine the error-location polynomial quickly because it is the most time consuming step. There are well known methods of computing the syndrome vector and finding the roots of the error-location polynomial that can be realized with fast electronic circuits. Thus, it is primarily the speed (time delay) with which the error-location polynomial can be found that determines the overall speed of the decoder. Became the invention can be realized by a combinational circuit, the only delays encounted are those of its individual logic elements. Thus the method of the invention can find the error-location polynomial for any three-error correcting BCH code at bit rates in the hundreds of megabits per second. The very feasibility of using BCH codes in high speed applications depends on how fast the decoder can operate. Thus, any speedup of the second decoding step (that of finding the error-location polynomial) allows a major advance in the applicability of real-time BCH codes to fast data transmission or storage systems.